package com.it.data_tree.tree.binarySearch;

/**
 * @Author: CaoYouGen
 * @DateTime: 2023/05/04/8:55
 * @注释: 二分查找（算法）
 **/
public class BinarySearch {
    
    /**
     * @param arr:   需要查找的数组
     * @param value: 需要查找的值
     * @return int
     * @Author: CaoYouGen
     * @注释: 二分查找（迭代实现）
     * @DateTime: 2023/5/4 9:00
     */
    public static Integer binarySearchIterative (int[] arr, int value) {
        // 1. 分别获取数组的 起始位置 和 末尾位置
        int min = 0;
        int max = arr.length;
        while (min < max) {
            // 2. 获取中间位置（用于比较）
//        int middle = (min + max) / 2;
            int middle = (min + max) >>> 1;
            // 3. 相等直接返回
            if (value == arr[middle]) {
                return middle;
                // 4. 往左找
            } else if (value < arr[middle]) {
                max = middle;
                // 5. 往右找
            } else {
                min = middle + 1;
            }
        }
        // 6.没有找到
        return - 1;
    }
    
    /**
     * @param arr:   需要查找的数组
     * @param value: 需要查找的值
     * @return Integer
     * @Author: CaoYouGen
     * @注释: 二分查找（递归实现）
     * @DateTime: 2023/5/4 9:13
     */
    public static Integer binarySearchRecursive (int[] arr, int value) {
        return doBinarySearchRecursive(arr, value, 0, arr.length - 1);
    }
    
    /**
     * @param arr:   需要查找的数组
     * @param value: 需要查找的值
     * @param min:   起始位置
     * @param max:   末尾位置1
     * @return Integer
     * @Author: CaoYouGen
     * @注释: 二分查找 -- 执行逻辑（递归实现）
     * @DateTime: 2023/5/4 9:23
     */
    private static Integer doBinarySearchRecursive (int[] arr, int value, int min, int max) {
        // 不存在，直接返回
        if (min > max) {
            return - 1;
        }
//        int middle = (min + max) / 2;
        int middle = (min + max) >>> 1;
        // 找到了 返回对应的索引
        if (value == arr[middle]) {
            return middle;
            // 往左找
        } else if (value < arr[middle]) {
            return doBinarySearchRecursive(arr, value, min, middle - 1);
            // 往右找
        } else {
            return doBinarySearchRecursive(arr, value, middle + 1, max);
        }
    }
    
    
    /**
     * @param arr:需要查找的数组
     * @param key:需要查找的值
     * @return int 返回最靠左的索引
     * @作者: Coke
     * @注释: TODO
     * @DateTime: 2023/5/7 14:25
     */
    public static int binarySearchLeftMost (int[] arr, int key) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int middle = (i + j) >>> 1;
            if (key <= arr[middle]) {
                j = middle - 1;
            } else {
                i = middle + 1;
            }
        }
        return arr[i] == key ? i : - i;
    }
    
    /**
     * @param arr:需要查找的数组
     * @param key:需要查找的值
     * @return int 返回最靠右的索引
     * @作者: Coke
     * @注释: TODO
     * @DateTime: 2023/5/7 14:25
     */
    public static int binarySearchRightMost (int[] arr, int key) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int middle = (i + j) >>> 1;
            if (key < arr[middle]) {
                j = middle - 1;
            } else {
                i = middle + 1;
            }
        }
        return arr[i - 1] == key ? i - 1 : - (i - 1);
    }
    
}
